麻豆淫院

As computing power continues to move from the desktop to portable devices, the nature of communications networks will change radically. A network in which devices are regularly being added and removed, and where the strength of the connections between the devices fluctuates with their movement, requires much different protocols from those that govern relatively stable networks, like the Internet.

In a in the December issue of the journal Distributed Computing, a group of researchers, including NEC Professor of Software Science and Engineering Nancy Lynch, describe a long-term project to give unstable networks stable, shared memory. Begun at MIT in 2001, and largely funded by the National Science Foundation, the project was initially envisioned as a means to preserve vital information for teams of soldiers operating in hostile environments, as, say, Tora Bora, Afghanistan, was at the time. But the work could also have ramifications for sensor networks, networks of mobile devices, peer-to-peer services on the Internet, and the large server farms that host heavily trafficked websites.

Because it was originally envisioned for military applications, the system has a very military-sounding acronym: RAMBO, for Reconfigurable Atomic Memory for Basic Objects. Suppose that soldiers are trying to secure a small village in hostile territory for a period of weeks. The composition of the teams patrolling the village will change constantly, but the soldiers need to stay abreast of the latest intelligence 鈥� which parts of the village are safe, for instance, and which could be dangerous. RAMBO is designed for situations in which the soldiers don鈥檛 have access to some central server that could store that type of information. The system distributes the information among the soldiers themselves, in such a way that, no matter who joins or leaves the network, everyone will always have access to the most recently updated information. The same system, however, could also preserve information about road conditions for ad hoc networks of sensor-laden cars, or allow emergency workers to quickly set up a shared data network when, for instance, a natural disaster has disrupted existing communications systems.

Virtual server

鈥淚t鈥檚 supposed to look like an instantaneously accessible memory, like if you have one machine in one location,鈥� Lynch says. 鈥淲e wanted to have that same appearance, but really, it鈥檚 running on mobile devices out in the field. There is no one machine.鈥� If someone on the network updates some shared information, rather than storing the update on a server, as an office network would, RAMBO sends multiple copies of the information to other devices on the network. But not all the devices, a simple majority of them. Similarly, when a device needs to retrieve information, it polls a simple majority of the other devices on the network. 鈥淭he thing about majorities is that any two of them have some copy in common,鈥� Lynch says. Suppose, for example, that there are five devices on the network, and an important piece of data is stored on three of them. If you randomly query any three of the five devices, at least one of them will have the data.

Difficulties arise, however, as the structure of the network changes. If just two devices storing the same piece of data leave a network 鈥� even a very large one 鈥� then querying a majority no longer guarantees the retrieval of that piece of data. The same is true if just two devices that aren鈥檛 storing the piece of data join the network. So RAMBO includes algorithms that recognize such changes and copy data to new devices in order to preserve majorities.

Earlier research in the field had investigated majority-based distributed memory systems, says Idit Keidar, an associate professor of electrical engineering at Technion, in Israel, who specializes in distributed systems. But 鈥渢he papers that presented these solutions, they didn鈥檛 deal with reconfiguration,鈥� she says. 鈥淩econfiguration, you don鈥檛 want to do it offline. You don鈥檛 want to bring the whole system down and then fix all the tables and then bring everything online again. What you want to do is to do it while the system鈥檚 working, with no down time. And that鈥檚 the problem that RAMBO鈥檚 trying to solve.鈥�

E pluribus unum

In some sense, Keidar says, RAMBO鈥檚 memory system and its reconfiguration system solve opposed problems. The memory system is designed so that each device on the network can store or retrieve information autonomously. It has to communicate with a majority of the other devices, but it doesn鈥檛 need to worry about what those devices are doing. It simply sends them data or requests data from them. But the reconfiguration system, Keidar says, requires the network to make some decisions as a whole. If a device at the edge of the network recognizes that several new devices have appeared nearby, it could start using them as part of its storage majority, but the rest of the network might not even know that they鈥檙e there. The researchers have actually proposed several different versions of RAMBO, optimized for different types of network. But during reconfiguration, they generally have to do some coordinating among devices.

Lynch鈥檚 two co-authors on the Distributed Computing paper have continued to build on the work they did on RAMBO at MIT. Seth Gilbert, who was a graduate student in Lynch鈥檚 lab and is now an assistant professor at the National University of Singapore, is working out the technical details of implementing RAMBO in wireless networks. Alex Shvartsman, a professor of computer science at the University of Connecticut who was a research associate and visiting scientist at MIT, is investigating applications of RAMBO for Internet file sharing.

Keidar, too, is working on a distributed-memory system, one that can reconfigure itself without having to do any coordinating among devices. That approach could prove more practical for some types of networks. But 鈥淩AMBO is seminal in inspiring that type of later work,鈥� Keidar says. 鈥淩AMBO defined the problem.鈥�

---

This story is republished courtesy of MIT News (), a popular site that covers news about MIT research, innovation and teaching.